#include "myTree.h"

using namespace std;



void TreeNode::printNode()
{
    cout << this->data;
}

TreeNode::TreeNode(char s, TreeNode* t1, TreeNode* t2, NodeTag a, NodeTag b)
{
    this->data = s;
    this->leftChild = t1;
    this->rightChild = t2;
    this->lTag = a;
    this->rTag = b;
}

MyTree::MyTree()
{
    f = 0;
    root = new TreeNode('1', NULL, NULL, Link, Link);
    root->leftChild = NULL;
}


MyTree::MyTree(const char s[])
{
    f = 0;
    root = new TreeNode('@', NULL, NULL, Link, Link);
    flag = 0;
    root->leftChild = creattree(s);
}

MyTree::MyTree(const MyTree& p)
{
    f = 0;
    root = new TreeNode;
    root->leftChild = copytree((p.root)->leftChild, (root->leftChild));
}

void MyTree::preOrderTraverse()
{
    stack<TreeNode*>s;
    TreeNode* p = root->leftChild;
    s.push(NULL);

    while (p != NULL)
    {
        p->printNode();
        if (p->rightChild != NULL)
        {
            s.push(p->rightChild);
        }
        if (p->leftChild != NULL)
        {
            p = p->leftChild;
        }
        else
        {
            p = s.top();
            s.pop();
        }
    }
}

void MyTree::inOrderTraverse()
{
    stack<TreeNode*>t;

    TreeNode* p = root->leftChild;
    if (p == NULL)
        return;
    if (f == 1)
    {
        while (!t.empty() || p != NULL)
        {
            while (p != NULL)
            {
                t.push(p);
                if (p->lTag == Link)
                {
                    p = p->leftChild;
                }
                else
                    p = NULL;
            }
            if (!t.empty())
            {
                p = t.top();
                p->printNode();
                t.pop();
                if (p->rTag == Link)
                {
                    p = p->rightChild;
                }
                else
                {
                    p = NULL;
                }
            }
        }
    }
    else
    {
        while (!t.empty() || p != NULL)
        {
            while (p != NULL)
            {
                t.push(p);
                p = p->leftChild;
            }
            if (!t.empty())
            {
                p = t.top();
                p->printNode();
                t.pop();
                p = p->rightChild;
            }
        }
    }
}

void MyTree::postOrderTraverse()
{
    typedef struct
    {
        TreeNode* ptr;
        bool isfirst;
    }stacknode;
    stack<stacknode>t;
    stacknode w;
    TreeNode* p = root->leftChild;
    do
    {
        while (p != NULL)
        {
            w.ptr = p;
            w.isfirst = true;
            t.push(w);
            p = p->leftChild;
        }
        int cot = 1;
        while (cot && !t.empty())
        {
            w = t.top();
            t.pop();
            p = w.ptr;
            switch (w.isfirst)
            {
            case true:
            {
                w.isfirst = false;
                t.push(w);
                cot = 0;
                p = p->rightChild;
                break;
            }
            case false: {p->printNode();
                if (p == root->leftChild)
                    return;
            }
            }
        }
    } while (p != NULL || !t.empty());
}

void MyTree::inthread(TreeNode* t)
{
    if (t != NULL)
    {
        inthread(t->leftChild);
        if (t->leftChild == NULL)
        {
            t->lTag = Thread;
            t->leftChild = pre;
        }
        if (pre->rightChild == NULL)
        {
            pre->rTag = Thread;
            pre->rightChild = t;
        }
        pre = t;
        inthread(t->rightChild);
    }
}

int MyTree::countLeaf()
{
    int sum = 0;
    stack<TreeNode*>s;
    TreeNode* p = root->leftChild;
    s.push(NULL);

    while (p != NULL)
    {
        if (p->leftChild == NULL && p->rightChild == NULL)
        {
            sum++;
        }
        if (p->rightChild != NULL)
        {
            s.push(p->rightChild);
        }
        if (p->leftChild != NULL)
        {
            p = p->leftChild;
        }
        else
        {
            p = s.top();
            s.pop();
        }

    }
    return sum;
}

int MyTree::countHeight()
{
    return cheight(root->leftChild);
}

bool MyTree::isThreadedTree()
{
    if (f == 0)
    {
        return false;
    }
    else
    {
        return true;
    }
}

TreeNode* MyTree::copytree(const TreeNode* t, TreeNode* tt)
{
    if (t == NULL)
    {

        return NULL;
    }
    else
    {
        tt = new TreeNode;
        tt->data = t->data;
        tt->leftChild = copytree(t->leftChild, tt->leftChild);
        tt->rightChild = copytree(t->rightChild, tt->rightChild);
        return tt;
    }
}


TreeNode& MyTree::preNode(const TreeNode& n)
{
    if (n.lTag == Thread && n.leftChild == root)
    {
        TreeNode* p = NULL;
        return *p;
    }
    if (n.lTag == Thread)
    {
        return *n.leftChild;
    }
    else
    {
        TreeNode* temp = n.leftChild;
        while (temp->rTag != Thread)
        {
            temp = temp->rightChild;
        }
        return *temp;
    }
}

TreeNode& MyTree::nextNode(const TreeNode& n)
{
    if (n.rTag == Thread && n.rightChild == root)
    {
        TreeNode* p = NULL;
        return *p;
    }
    if (n.rTag == Thread)
    {
        return *n.rightChild;
    }
    else
    {
        TreeNode* temp = n.rightChild;
        while (temp->lTag != Thread)
        {
            temp = temp->leftChild;
        }
        return *temp;
    }
}

HuffmanTree::HuffmanTree(const int& n, int s[])
{
    {
        len = 2 * n - 1;
        tree = new point[2 * n - 1];
        for (int i = 0; i < n; i++)
        {
            tree[i].weight = s[i];
        }
        for (int i = 0; i < 2 * n - 1; i++)
        {
            tree[i].lchild = -1;
            tree[i].rchild = -1;
            tree[i].parent = -1;
        }
        for (int i = n; i < 2 * n - 1; i++)
        {
            int min1 = 100000000;
            int min2 = 100000000;
            int pos1 = 0, pos2;
            for (int j = 0; j < i; j++)
            {
                if (tree[j].parent == -1)
                {
                    if (tree[j].weight < min1)
                    {
                        pos2 = pos1;
                        min2 = min1;
                        pos1 = j;
                        min1 = tree[j].weight;
                    }
                    else if (tree[j].weight < min2)
                    {
                        pos2 = j;
                        min2 = tree[j].weight;
                    }
                }
            }
            tree[i].lchild = pos1;
            tree[i].rchild = pos2;
            tree[i].weight = tree[pos1].weight + tree[pos2].weight;
            tree[pos1].parent = i;
            tree[pos2].parent = i;
        }
    }

}


TreeNode& MyTree::locateNode(const char& v)
{

    stack<TreeNode*>t;

    TreeNode* p = root->leftChild;

    if (f == 1)
    {
        while (!t.empty() || p != NULL)
        {
            while (p != NULL)
            {
                t.push(p);
                if (p->lTag == Link)
                {
                    p = p->leftChild;
                }
                else
                    p = NULL;
            }
            if (!t.empty())
            {
                p = t.top();
                if (p->data == v)
                {
                    return *p;
                }
                t.pop();
                if (p->rTag == Link)
                {
                    p = p->rightChild;
                }
                else
                {
                    p = NULL;
                }
            }
        }
    }
    else
    {
        while (!t.empty() || p != NULL)
        {
            while (p != NULL)
            {
                t.push(p);
                p = p->leftChild;
            }
            if (!t.empty())
            {
                p = t.top();
                if (p->data == v)
                {
                    return *p;
                }
                t.pop();
                p = p->rightChild;
            }
        }
    }
    TreeNode* temp = NULL;
    return *temp;
}

//int main()
//{
//    MyTree myTree("ABC@@DE@G@@F@@@");
//    myTree.preOrderTraverse();//ABCDEGF
//    cout << endl;
//    myTree.inOrderTraverse();//CBEGDFA
//    cout << endl;
//    myTree.postOrderTraverse();//CGEFDBA
//    cout << endl;
//    cout << myTree.countLeaf() << endl;//3
//    cout << myTree.countHeight() << endl;//5
//
//    MyTree myThreadedTree(myTree);
//    cout << myThreadedTree.isThreadedTree() << endl;//0
//    myThreadedTree.inOrderThreading();
//    cout << myThreadedTree.isThreadedTree() << endl;//1
//    myThreadedTree.inOrderTraverse();//CBEGDFA
//    cout << endl;
//
//    TreeNode n = myThreadedTree.locateNode('G');
//    myThreadedTree.preNode(n).printNode();//E
//    cout << endl;
//    myThreadedTree.nextNode(n).printNode();//D
//    cout << endl;
//
//    int v[] = { 2,7,5,4 };
//    HuffmanTree hTree(4, v);
//    hTree.printHuffmanCodes();
//    /*
//    7:0
//    5:10
//    4:111
//    2:110
//    */
//
//    return 0;
//}